package com.shixianjun.leetcode;

public class _88_合并两个有序数组 {


    static public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m - 1; i >= 0; i--) {
            nums1[i + n] = nums1[i];
        }
        int i1 = 0, i2 = 0;
        int index = 0;

        while (i1 < m && i2 < n) {
            nums1[index++] = nums1[n + i1] < nums2[i2] ? nums1[n + i1++] : nums2[i2++];
        }

        while (i2 < n) {
            nums1[index++] = nums2[i2++];
        }
    }

    // 优化 逆向思维 从大到小 不再需要移动数据
    static public void merge2(int[] nums1, int m, int[] nums2, int n) {

        int i1 = m - 1, i2 = n - 1;
        int index = nums1.length - 1;

        while (i1 >= 0 && i2 >= 0) {
            nums1[index--] = nums1[i1] > nums2[i2] ? nums1[i1--] : nums2[i2--];
        }

        while (i2 >= 0) {
            nums1[index--] = nums2[i2--];
        }
    }

    public static void main(String[] args) {
        int[] num1 = {1, 2, 3, 0, 0, 0};
        int m = 3;
        int[] num2 = {2, 5, 6};
        int n = 3;

        merge2(num1, m, num2, n);

        for (int i : num1) {
            System.out.print(i + " ");
        }
    }
}
